5th Year Thesis Presentation - William Seo___

— 3:00pm

Location:
In Person - Traffic21 Classroom, Gates Hillman 6501

Speaker:
WILLIAM SEO, Master's Student, Computer Science Department, Carnegie Mellon University

Level Aware Bootstrapping Placement for Fully Homomorphic Encryption Using MaxSAT

Fully Homomorphic Encryption (FHE) is a cryptographic technique that allows computations to be performed on encrypted data without having to decrypt it. This property preserves data privacy, enabling a wide range of applications in fields such as cloud computing, secure data analysis, and privacy-preserving machine learning. 

In FHE computations, each ciphertext can only handle a limited number of operations before the accumulation of noise makes decryption impossible. To resolve this, the bootstrapping operation must be used to reset the noise in the ciphertext. Bootstrapping is a computationally expensive computation, and it influences the costs of other operations. Consequently, the strategic placement of bootstrapping operations is a critical aspect of FHE performance. 

This thesis introduces Saturn, a novel method for automatically determining the placement of bootstrapping operations which minimizes program runtime. Given a directed acyclic graph (DAG) representing an FHE computation, Saturn leverages the Maximum Satisfiability (MaxSAT) optimization problem to find the most efficient bootstrapping placement. Additionally, we propose two methods for reducing the complexity of the input computational DAG, significantly decreasing the solve time of our MaxSAT formulation. Saturn's effectiveness is evaluated on various deep learning models, demonstrating its potential to enhance FHE performance.

Thesis Committee:

Wenting Zheng (Chair)
Fraser Brown

Additional Information

Event Website:
https://csd.cmu.edu/calendar/5th-year-thesis-SEO-2024-07-22